package MiniSpanTree;

import Graph.GraphKind;
import Graph.MGraph;

public class MiniSpanTree_Kruskal {public final static int INFINITY = Integer.MAX_VALUE;

    public static Object[][] KRUSKAL(MGraph G) throws Exception {
        Object[][] tree = new Object[G.getVexNum() - 1][2];// 存储最小生成树的边
        EqualClass A = new EqualClass(G);// 等价类数组
        MinHeap H = new MinHeap(G);// 用图G的边构造一个最小堆
        int count = 0;
        while (count < G.getVexNum() - 1) {// 用G.vexnum – 1条边构成最小生成树
            Object[] vexs = H.removeMin();// 取堆上最小边
            Object u = vexs[0];
            Object v = vexs[1];
            if (A.differ(u, v)) {// 如果u,v不在同一等价类中
                A.union(u, v);// 合并到同一等价类
                tree[count][0] = u;// 生成树的边放入数组中
                tree[count][1] = v;
                count++;
            }
        }

        return tree;
    }

    static class MinHeapNode {
        private Object[] vexs;// 边的两个顶点

        private int key;// 边的权值

        public MinHeapNode(Object[] vexs, int key) {
            this.vexs = vexs;
            this.key = key;
        }

        public Object[] getVexs() {
            return vexs;
        }

        public int getKey() {
            return key;
        }

    }

    static class MinHeap {

        private MinHeapNode[] heapArray;; // 堆容器

        private int maxSize; // 堆得最大大小

        private int currentSize; // 堆大小

        public MinHeap(MGraph G) throws Exception {
            maxSize = G.getVexNum() * G.getVexNum();
            heapArray = new MinHeapNode[maxSize];
            currentSize = 0;
            for (int i = 0; i < G.getVexNum(); i++) {
                for (int j = i + 1; j < G.getVexNum(); j++) {
                    Object[] vexs = { G.getVex(i), G.getVex(j) };
                    MinHeapNode newNode = new MinHeapNode(vexs,
                            G.getArcs()[i][j]);
                    insert(newNode);
                }
            }
        }

        // 自上而下调整
        public void filterDown(int start, int endOfHeap) {
            int i = start;
            int j = 2 * i + 1; // j是i的左子女位置
            MinHeapNode temp = heapArray[i];

            while (j <= endOfHeap) { // 检查是否到最后位置
                if (j < endOfHeap // 让j指向两子女中的小者
                        && heapArray[j].getKey() > heapArray[j + 1].getKey()) {
                    j++;
                }
                if (temp.getKey() <= heapArray[j].getKey()) { // 小则不做调整
                    break;
                } else { // 否则小者上移，i，j下降
                    heapArray[i] = heapArray[j];
                    i = j;
                    j = 2 * j + 1;
                }
            }
            heapArray[i] = temp;
        }

        // 自下而上的调整:从结点start开始到0为止，自下向上比较，如果子女的值小于双亲结点的值则互相交换
        public void filterUp(int start) {
            int j = start;
            int i = (j - 1) / 2;
            MinHeapNode temp = heapArray[j];

            while (j > 0) { // 沿双亲结点路径向上直达根节点
                if (heapArray[i].getKey() <= temp.getKey()) {// 双亲结点值小，不调整
                    break;
                } else {// 双亲结点值大，调整
                    heapArray[j] = heapArray[i];
                    j = i;
                    i = (i - 1) / 2;
                }
                heapArray[j] = temp; // 回送
            }
        }

        // 堆中插入结点
        public void insert(MinHeapNode newNode) {
            heapArray[currentSize] = newNode;
            filterUp(currentSize);
            currentSize++;
        }

        // 删除堆中的最小值
        public Object[] removeMin() {
            MinHeapNode root = heapArray[0];
            heapArray[0] = heapArray[currentSize - 1];
            currentSize--;
            filterDown(0, currentSize - 1);
            return root.getVexs();
        }

    }

    static class EqualClass {
        private Object[] S;// 存放已经选择过的顶点

        private Object[] V;// 存放未选择的顶点

        EqualClass(MGraph G) {
            S = new Object[G.getVexNum()];
            V = new Object[G.getVexNum()];
            System.arraycopy(G.getVexs(), 0, V, 0, G.getVexs().length);
        }

        public boolean differ(Object u, Object v) {
            boolean isDiffer = false;
            int count = 0;
            for (int i = 0; i < V.length; i++) {
                if (V[i] != null && (V[i].equals(u) || V[i].equals(v)))
                    ++count;
            }

            if (count == 0 || count == 2)
                isDiffer = true;

            return isDiffer;
        }

        public void union(Object u, Object v) {
            boolean isHaveU = false;// u点是否已经被选择
            boolean isHaveV = false;
            int i = 0;
            for (; i < S.length && S[i] != null; i++) {
                if (S[i].equals(u))
                    isHaveU = true;
                else if (S[i].equals(v))
                    isHaveV = true;

            }

            if (!isHaveU)
                S[i] = u;

            if (!isHaveV)
                S[i] = v;

        }
    }

    public static void main(String[] args) throws Exception {
        Object vexs[] = { "A", "B", "C", "D", "E", "F","G","H","I","J","K", "L", "M", "N", "O", "P","Q","R","S","T" };
        int[][] arcs = {     {INFINITY,11,52,80,68,47, 8,34,38,40,96,73,81,47,13,55,88, 7,75,33},
                {11, INFINITY,37,13,52, 4,12,58,25,76, 9,69,21,71,12,45,84,31,90,73},
                {52,37, INFINITY,82, 5,91,59,67,40,68,51,14,76,69,14,62,66,83,77, 8},
                {80,13,82, INFINITY,88,26,11,76,57,40,47,55,65,78,94,94,29,17,96,88},
                {68,52, 5,88, INFINITY,52,23,55,59, 1,30,12,85,84,28,43,41,13,12,58},
                {47, 4,91,26,52, INFINITY,90, 7,16,11,42, 9,83,31,64,20,96, 6,69,96},
                { 8,12,59,11,23,90, INFINITY,54,24,26,96,54,52,82,80,58,45,69,98,39},
                {34,58,67,76,55, 7,54, INFINITY,40, 7, 8,54,19,27,27,11,53,15,12,40},
                {38,25,40,57,59,16,24,40, INFINITY,66, 3,15,61, 9,19,25,68, 6, 4,89},
                {40,76,68,40, 1,11,26, 7,66, INFINITY,67,46,40,40,92,37,27,16, 2,84},
                {96, 9,51,45,30,42,96, 8, 3,67, INFINITY,31,91,62,71,68,17,22,82,24},
                {73,69,14,55,12, 9,54,54,15,46,31, INFINITY, 6,46,26,72,79,14,21,26},
                {81,21,76,65,85,83,52,19,61,40,91, 6, INFINITY,70,95,34,65,53,30,52},
                {47,71,69,78,84,31,82,27, 9,40,62,46,70, INFINITY,19, 2,47,74,58,85},
                {13,12,14,94,28,64,80,27,19,92,71,26,95,19, INFINITY,27,99,21, 9,74},
                {55,45,62,94,43,20,58,11,25,37,68,72,34, 2,27, INFINITY, 1,63,13,17},
                {88,84,66,29,41,96,45,53,68,27,17,79,65,47,99, 1, INFINITY,33,44, 8},
                { 7,31,83,17,13, 6,69,15, 6,16,72,14,53,74,21,63,33, INFINITY,79,41},
                {75,90,77,96,12,69,98,12, 4, 2,82,21,30,58, 9,13,44,79, INFINITY, 4},
                {33,73, 8,88,58,96,39,40,89,84,24,26,52,85,74,17, 8,41, 4, INFINITY,}};
        MGraph G = new MGraph(GraphKind.UDG,20, 30, vexs, arcs);
        Object[][] T = MiniSpanTree_Kruskal.KRUSKAL(G);
        for (int i = 0; i < T.length; i++)
            System.out.println(T[i][0] + " - " + T[i][1]);
    }
}

